Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

Description

墨墨突然对等式很感兴趣,他正在研究 \(a_1x_1+a_2x_2+...+a_nx_n=B\) 存在非负整数解的条件,他要求你编写一个程序,给定 \(N\)\(\{a_n\}\)、以及 \(B\) 的取值范围,求出有多少 \(B\) 可以使等式存在非负整数解。

Input

输入的第一行包含 3 个正整数,分别表示 \(N\)\(B_{Min}\)\(B_{Max}\) 分别表示数列的长度、\(B\) 的下界、\(B\) 的上界。输入的第二行包含 \(N\) 个整数,即数列 \(\{a_n\}\) 的值。

Output

输出一个整数,表示有多少b可以使等式存在非负整数解。

Sample Input

2 5 10
3 5

Sample Output

5

HINT

对于 100% 的数据,\(N\leq 12\)\(0\leq a_i\leq 5*10^5\)$,\(1\leq B_{Min},B_{Max}\leq 10^{12}\)

分析

我们发现这已经不是简单的数论题了!(我开始并没有发现)对于这种无限取的背包问题,可以转化为取 mod 最短路的问题。具体怎么想呢?

首先我们将 \(a\) 排序(因为这道题 \(n\) 比较小其实可以不用但是这样更优秀)考虑对于 \(a_1\),对于所有能够取到的数 \(x\),都有 \(x+a1*k\)\(k\) 任意)一定会被取到。所以我们就可以把所有能够取到的数模 \(a_1\),发现结果属于 \(0,\dots, a_1-1\)中的一个,那么我们就把每一个 \(0,\dots, a_1\) 看做一个集合包括所有能够取到的数模 \(a_1\) 等于该值。

那么最小路怎么解释呢?相当于每次加一个数就走了一条边,我们将所有小于 \(r\) 的数模 \(a_1\) 的最小值看做最短路,求完后遍历 \(0,\dots,a_1\) 分别求 \(r\)\(l-1\) 的组合的个数(前缀和)减去即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<algorithm>
#include<cstring>
#include<queue>
#include<utility>
#include<vector>
#include<functional>
using namespace std;
const int maxn=5e5+5;
typedef long long ll;
typedef pair<ll,int> pairr;

int n,a[15];
ll L, R;

struct Edge{
int to,nxt,dis;
}e[maxn*10];

int head[maxn];int ecnt;

inline void addedge(int from,int to,int dis)
{
e[++ecnt]=(Edge){to,head[from],dis},head[from]=ecnt;
}

ll dis[maxn];
bool vis[maxn];
void dijkstra()
{
priority_queue <pairr,vector<pairr >,greater<pairr > >q;
for(int i=0;i<a[1];i++)dis[i]=(ll)1e60;
dis[0]=0;
q.push(make_pair(0,0));
while(!q.empty())
{
int v=q.top().second;q.pop();
if(vis[v])continue;vis[v]=1;
for(int i=head[v];i!=-1;i=e[i].nxt)
{
int u=e[i].to;
ll w=(ll)e[i].dis;
if(dis[u]>dis[v]+w)
{
dis[u]=dis[v]+w;
q.push(make_pair(dis[u],u));
}
}
}
}

inline ll getans(ll x)
{
ll ans=0;
for(int i=0;i<a[1];i++)
if(dis[i]<=R){
ll zp=max(0ll,(x-dis[i])/a[1]);
if(zp*a[1]+dis[i]<x)ans++;
ans+=zp;
}
return ans;
}

int main()
{
scanf("%d%lld%lld",&n,&L,&R);
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==0)n--,i--;
}
sort(a+1,a+1+n);
for(int i=0;i<a[1];i++)
for(int j=2;j<=n;j++)
addedge(i,(a[j]+i)%a[1],a[j]);
dijkstra();
// printf("%lld\n",getans(R)-getans(L-1)+1);
ll ans=0;
for (int i=0;i<a[1];i++) if (dis[i]<=R) {
ll l=max(0ll,(L-dis[i])/a[1]);
if (l*a[1]+dis[i]<L) l++;
ll r=(R-dis[i])/a[1];
if (r*a[1]+dis[i]>R) r--;
ans+=r-l+1;
}
printf("%lld\n",ans);
return 0;
}

给小狼留言